package 前序中序还原二叉树;
import 相同的树.TreeNode;

class Solution {
    //将preindex定义为成员变量,防止在回溯途中发生问题
    public int preindex = 0;
    //给前序遍历序列与中序遍历序列创建二叉树
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //调用方法buildTreeChild返回创建二叉树的根结点
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    //将树中每棵子树的根结点创建出来并在回溯途中连在一起
    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int inbegin,int inend) {
        //当开始位置大于结束位置递归结束,当前树为空树
        if (inbegin > inend){
            return null;
        }
        //创建根结点root接收当前创建的根结点
        TreeNode root = new TreeNode(preorder[preindex]);
        //找到当前根结点在中序遍历序列中的位置
        int index = findpos(inorder,inbegin,inend,preorder[preindex]);
        //preindex++移动到下一个根结点的位置
        preindex++;
        //index为-1说明没有在中序遍历序列中找到当前根结点
        if (index == -1){
            return null;
        }
        //递归调用,开始创建当前根结点的左右子树
        //左子树的中序遍历序列就是中序遍历起始位置到当前根结点在中序遍历序列中位置
        root.left = buildTreeChild(preorder,inorder,inbegin,index-1);
        //右子树的中序遍历序列就是当前根结点在中序遍历序列中位置到中序遍历结束位置
        root.right = buildTreeChild(preorder,inorder,index+1,inend);
        //返回当前根结点
        return root;
    }
    //在中序遍历中寻找当前树中根结点的位置
    private int findpos(int[] inorder, int inbegin, int inend,int pos) {
        //从开始位置顺序查找根结点的位置
        for (int i = inbegin;i <= inend;i++){
            if (inorder[i] == pos){
                //找到返回根结点在中序遍历序列中的位置
                return i;
            }
        }
        //没找到返回-1
        return -1;
    }
}